1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
/*!
S-expressions
*/

use super::*;
use once_cell::sync::OnceCell;

/// An S-expression
#[derive(Clone, Eq)]
pub struct Sexpr {
    /// The function being applied
    func: ValId,
    /// The argument it is being applied to
    arg: ValId,
    /// The cached type of this expression
    ty: ValId,
    /// The cached hash code of this expression
    code: u64,
    /// The free-variable set of this expression
    fv: SymbolSet,
    /// The constraint-set of this application
    constraints: Constraints,
    /// The normalized form of this S-expression
    normal_form: OnceCell<Option<ValId>>,
}

impl Sexpr {
    /// Try to construct a new S-expression
    pub fn try_new(func: ValId, arg: ValId) -> Result<Sexpr, Error> {
        let (ty, constraints) = func.ty().apply_ty(&arg)?.rectify(func.clone());
        let result = Self::new_unchecked(func, arg, ty, constraints);
        Ok(result)
    }
    /// Create a new, unchecked S-expression
    pub(super) fn new_unchecked(
        func: ValId,
        arg: ValId,
        ty: ValId,
        constraints: Constraints,
    ) -> Sexpr {
        let fv = func.fv().union(arg.fv());
        let mut hasher = Self::get_hasher();
        func.code().hash(&mut hasher);
        arg.code().hash(&mut hasher);
        let code = hasher.finish();
        Sexpr {
            func,
            arg,
            ty,
            code,
            fv,
            constraints,
            normal_form: OnceCell::new(),
        }
    }
    /// Get the hasher used for S-expressions
    #[inline]
    pub fn get_hasher() -> AHasher {
        AHasher::new_with_keys(312, 123)
    }
}

impl Value for Sexpr {
    #[inline]
    fn is_kind(&self) -> bool {
        false
    }
    #[inline]
    fn ty(&self) -> &ValId {
        &self.ty
    }
    #[inline]
    fn into_enum(self) -> ValueEnum {
        ValueEnum::Sexpr(self)
    }
    #[inline]
    fn code(&self) -> u64 {
        self.code
    }
    #[inline]
    fn fv(&self) -> &SymbolSet {
        &self.fv
    }
    #[inline]
    fn local_constraints(&self) -> &Constraints {
        &self.constraints
    }
    fn eval_in_ctx(&self, ctx: &mut EvalCtx) -> Option<ValId> {
        if ctx.is_null() {
            return None;
        }
        if ctx.is_empty() && ctx.is_normalizing() {
            return self.normalized().cloned();
        }
        let arg = self.arg.eval_in_ctx(ctx);
        let result = if ctx.is_normalizing() {
            self.func
                .apply_in_ctx(&self.arg, ctx)
                .expect("Applying substituted argument should never fail")
        } else {
            let func = self.func.eval_in_ctx(ctx);
            if func.is_none() && arg.is_none() {
                return None;
            }
            Sexpr::try_new(
                func.unwrap_or_else(|| self.func.clone()),
                arg.unwrap_or_else(|| self.arg.clone()),
            )
            .expect("Substituted sexpr construction should never fail")
            .into_valid()
        };
        Some(result)
    }
    fn try_apply_in_ctx(&self, arg: &ValId, ctx: &mut EvalCtx) -> Result<Application, Error> {
        if ctx.is_normalizing() {
            if let Some(normal) = self.eval_in_ctx(ctx) {
                return normal.try_apply_in_ctx(arg, ctx);
            }
        }
        Ok(Application::Abstract(None))
    }
    fn normalized(&self) -> Option<&ValId> {
        self.normal_form
            .get_or_init(|| {
                let (func, arg) = match (self.func.normalized(), self.arg.normalized()) {
                    (None, None) => match self
                        .func
                        .try_apply_norm(&self.arg)
                        .expect("Valid sexprs always yield a valid application")
                    {
                        Application::Abstract(_) => return None,
                        Application::Concrete(value) => {
                            debug_assert!(
                                value.is_normal(),
                                "Evaluated in normalizing context, so result should be normal!"
                            );
                            return Some(value);
                        }
                    },
                    (Some(func), None) => (func, &self.arg),
                    (None, Some(arg)) => (&self.func, arg),
                    (Some(func), Some(arg)) => (func, arg),
                };
                let result = Sexpr::new_unchecked(
                    func.clone(),
                    arg.clone(),
                    self.ty
                        .normalized()
                        .cloned()
                        .unwrap_or_else(|| self.ty.clone()),
                    self.constraints.clone(),
                );
                let result_valid = result.normalized().cloned();
                Some(result_valid.unwrap_or_else(|| result.into_valid()))
            })
            .as_ref()
    }
}

impl PartialEq for Sexpr {
    fn eq(&self, other: &Sexpr) -> bool {
        self.func == other.func && self.arg == other.arg
    }
}

impl Debug for Sexpr {
    fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
        fmt.debug_tuple("Sexpr")
            .field(&self.func)
            .field(&self.arg)
            .finish()
    }
}

impl Hash for Sexpr {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.func.hash(hasher);
        self.arg.hash(hasher)
    }
}